﻿using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Grafos;

namespace GrafosTestUnit {
    /// <summary>
    /// Testes na classe GrafoPonderado
    /// </summary>
    [TestClass]
    public class TesteGrafoPonderado {

        /// <summary>
        /// Detecção de arestas paralelas
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria os vértices V1, V2, V3
        /// Cria as arestas A1=(V1, V2): 5, A2=(V2, V3): 10, A3=(V1, V2): 15
        /// Cria o grafo G
        /// Adiciona os vértices a G
        /// Adiciona as arestas a G
        /// Verifica-se:
        /// G possui aresta paralela a A1
        /// G possui aresta paralela a V2-V3
        /// G possui aresta paralela a V1-V3
        /// G não possui aresta paralela a A2
        /// </remarks>
        [TestMethod]
        public void ArestasParalelas() {
            GrafoPonderado g;
            Vértice v1, v2, v3;
            ArestaPonderada a1, a2, a3;

            v1 = new Vértice("GP1");
            v2 = new Vértice("GP2");
            v3 = new Vértice("GP3");

            a1 = new ArestaPonderada(v1, v2, 5);
            a2 = new ArestaPonderada(v2, v3, 10);
            a3 = new ArestaPonderada(v1, v2);
            a3.Valor = 15;

            g = new GrafoPonderado();

            g.AdicionarVértice(v1);
            g.AdicionarVértice(v2);
            g.AdicionarVértice(v3);

            g.AdicionarAresta(a1);
            g.AdicionarAresta(a2);
            g.AdicionarAresta(v1, v3);

            Assert.IsTrue(g.PossuiArestaParalela(a1)); // a1 paralela a a3
            Assert.IsTrue(g.PossuiArestaParalela(v2, v3)); // a2 é paralela a v2-v3
            Assert.IsTrue(g.PossuiArestaParalela(v1, v3)); // aresta adicionada manualmente v1-v3

            Assert.IsFalse(g.PossuiArestaParalela(a2)); // nenhuma aresta fora a2 é paralela a a2
        }

        /// <summary>
        /// Testa se o grafo ponderado detecta loops corretamente
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria um grafo G, com vértices A e B, e arestas A-B, A-B, B-A e A-B
        /// Verifica que G não possui loops
        /// Adiciona aresta A-A
        /// Verifica que G possui loop
        /// </remarks>
        [TestMethod]
        public void PossuiLoops() {
            GrafoPonderado g;

            g = new GrafoPonderado();
            g.AdicionarVértice("A", "B");
            g.AdicionarAresta("A", "B", 5);
            g.AdicionarAresta("B", "A", 4);
            g.AdicionarAresta("A", "B", 2);

            Assert.IsFalse(g.PossuiLoop());

            g.AdicionarAresta("A", "A");
            Assert.IsTrue(g.PossuiLoop());
        }

        /// <summary>
        /// Testa se o grafo ponderado detecta ciclos corretamente
        /// </summary>
        /// <remarks>
        /// Proceso:
        /// Cria os grafos G1, G2, G3 e G4, todos com os vértices A, B e C
        /// Criam-se as seguintes arestas:
        /// G1: nenhuma
        /// G2: A-A
        /// G3: A-B, A-C, B-C
        /// G4: A-B, B-C
        /// Verifica-se:
        /// G1 não possui ciclo
        /// G2 possui ciclo
        /// G3 possui ciclo
        /// G4 não possui ciclo
        /// </remarks>
        [TestMethod]
        public void PossuiCiclo() {
            GrafoPonderado g1, g2, g3, g4;

            g1 = new GrafoPonderado();
            g1.AdicionarVértice("A", "B", "C");

            g2 = (GrafoPonderado)g1.Cópia();
            g3 = (GrafoPonderado)g1.Cópia();
            g4 = (GrafoPonderado)g1.Cópia();

            g2.AdicionarAresta("A", "A");

            g3.AdicionarAresta("A", "B");
            g3.AdicionarAresta("A", "C");
            g3.AdicionarAresta("B", "C");

            g4.AdicionarAresta("A", "B");
            g4.AdicionarAresta("B", "C");

            Assert.IsFalse(g1.PossuiCiclo());
            Assert.IsTrue(g2.PossuiCiclo());
            Assert.IsTrue(g3.PossuiCiclo());
            Assert.IsFalse(g4.PossuiCiclo());
        }


        /// <summary>
        /// Teste do Algoritmo de Kruskal
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria um grafo G com vértices A..J e arestas:
        /// A-B: 12
        /// A-D: 10
        /// B-C: 5
        /// C-D: 7
        /// C-E: 4
        /// E-F: 12
        /// E-G: 3
        /// F-G: 12
        /// E-H: 1
        /// H-I: 6
        /// H-J: 3
        /// I-J: 4
        /// Cria a árvore AP, definida pelo algoritmo de Kruskal aplicado em G
        /// Verifica-se:
        /// AP possui as arestas A-D, C-D, B-C, C-E, E-F, E-G, E-H, H-J, J-I
        /// AP possui 10 vértices
        /// AP possui 9 arestas
        /// </remarks>
        [TestMethod]
        public void TesteAlgoritmoKruskal() {
            GrafoPonderado g;
            ÁrvorePonderada ap;
            Vértice[] v = new Vértice[10];
            char c = 'A';

            g = new GrafoPonderado();

            for (int i = 0; i < 10; i++) {
                v[i] = new Vértice(c.ToString());
                c++;
                g.AdicionarVértice(v[i]);
            }

            g.AdicionarAresta(v[0], v[1], 12); // A-B
            g.AdicionarAresta(v[0], v[3], 10); // A-D
            g.AdicionarAresta(v[1], v[2], 5); // B-C
            g.AdicionarAresta(v[2], v[3], 7); // C-D
            g.AdicionarAresta(v[2], v[4], 4); // C-E
            g.AdicionarAresta(v[4], v[5], 12); // E-F
            g.AdicionarAresta(v[4], v[6], 3); // E-G
            g.AdicionarAresta(v[5], v[6], 12); // F-G
            g.AdicionarAresta(v[4], v[7], 1); // E-H
            g.AdicionarAresta(v[7], v[8], 6); // H-I
            g.AdicionarAresta(v[7], v[9], 3); // H-J
            g.AdicionarAresta(v[8], v[9], 4); // I-J

            ap = g.Kruskal();

            for (int i = 0; i < 10; i++) {
                v[i] = ap.BuscarVértice(v[i].Nome);
            }

            Assert.IsTrue(ap.PossuiArestaParalela(v[0], v[3])); // A-D
            Assert.IsTrue(ap.PossuiArestaParalela(v[2], v[3])); // C-D
            Assert.IsTrue(ap.PossuiArestaParalela(v[1], v[2])); // B-C
            Assert.IsTrue(ap.PossuiArestaParalela(v[2], v[4])); // C-E
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[5])); // E-F
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[6])); // E-G
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[7])); // E-H
            Assert.IsTrue(ap.PossuiArestaParalela(v[7], v[9])); // H-J
            Assert.IsTrue(ap.PossuiArestaParalela(v[9], v[8])); // J-I
            Assert.AreEqual(10, ap.QuantidadeVértices);
            Assert.AreEqual(9, ap.QuantidadeArestas);
        }

        /// <summary>
        /// Teste do Algoritmo de Djikstra
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Define um grafo G igual ao definido no teste do algoritmo de Kruskal
        /// Cria a árvore AP, definida pelo algoritmo de Djikstra aplicado em G, com raíz no vértice E
        /// Verifica-se:
        /// AP possui 10 vértices
        /// AP possui 9 arestas
        /// AP possui as arestas A-B, B-C, C-D, C-E, E-F, E-G, E-H, H-I, H-J
        /// </remarks>
        [TestMethod]
        public void TesteAlgoritmoDjikstra() {
            GrafoPonderado g;
            ÁrvorePonderada ap;
            Vértice[] v = new Vértice[10];
            char c = 'A';

            g = new GrafoPonderado();

            for (int i = 0; i < 10; i++) {
                v[i] = new Vértice(c.ToString());
                c++;
                g.AdicionarVértice(v[i]);
            }

            g.AdicionarAresta(v[0], v[1], 12); // A-B
            g.AdicionarAresta(v[0], v[3], 10); // A-D
            g.AdicionarAresta(v[1], v[2], 5); // B-C
            g.AdicionarAresta(v[2], v[3], 7); // C-D
            g.AdicionarAresta(v[2], v[4], 4); // C-E
            g.AdicionarAresta(v[4], v[5], 12); // E-F
            g.AdicionarAresta(v[4], v[6], 3); // E-G
            g.AdicionarAresta(v[5], v[6], 12); // F-G
            g.AdicionarAresta(v[4], v[7], 1); // E-H
            g.AdicionarAresta(v[7], v[8], 6); // H-I
            g.AdicionarAresta(v[7], v[9], 3); // H-J
            g.AdicionarAresta(v[8], v[9], 4); // I-J

            ap = g.Djikstra(v[4]);

            for (int i = 0; i < 10; i++) {
                v[i] = ap.BuscarVértice(v[i].Nome);
            }

            Assert.IsTrue(ap.PossuiArestaParalela(v[0], v[1])); // A-B
            Assert.IsTrue(ap.PossuiArestaParalela(v[1], v[2])); // B-C
            Assert.IsTrue(ap.PossuiArestaParalela(v[2], v[3])); // C-D
            Assert.IsTrue(ap.PossuiArestaParalela(v[2], v[4])); // C-E
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[5])); // E-F
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[6])); // E-G
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[7])); // E-H
            Assert.IsTrue(ap.PossuiArestaParalela(v[7], v[8])); // H-I
            Assert.IsTrue(ap.PossuiArestaParalela(v[7], v[9])); // H-J
            Assert.AreEqual(9, ap.QuantidadeArestas);
            Assert.AreEqual(10, ap.QuantidadeVértices);
        }

        /// <summary>
        /// Testa o algoritmo de Djisktra passando múltiplas raízes
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Define um grafo G igual ao definido no teste do algoritmo de Kruskal
        /// Cria a árvore AP, definida pelo algoritmo de Djikstra aplicado em G, com raízes nos vértices A, E e J
        /// Verifica-se:
        /// AP possui 10 vértices
        /// AP possui 7 arestas
        /// AP possui as arestas A-D, B-C, C-E, E-F, E-G, E-H, I-J
        /// AP possui 3 componentes conexos
        /// </remarks>
        [TestMethod]
        public void DjisktraMúltiplasRaízes() {
            GrafoPonderado g;
            ÁrvorePonderada ap;
            Vértice[] v = new Vértice[10];
            char c = 'A';

            g = new GrafoPonderado();

            for (int i = 0; i < 10; i++) {
                v[i] = new Vértice(c.ToString());
                c++;
                g.AdicionarVértice(v[i]);
            }

            g.AdicionarAresta(v[0], v[1], 12); // A-B
            g.AdicionarAresta(v[0], v[3], 10); // A-D
            g.AdicionarAresta(v[1], v[2], 5); // B-C
            g.AdicionarAresta(v[2], v[3], 7); // C-D
            g.AdicionarAresta(v[2], v[4], 4); // C-E
            g.AdicionarAresta(v[4], v[5], 12); // E-F
            g.AdicionarAresta(v[4], v[6], 3); // E-G
            g.AdicionarAresta(v[5], v[6], 12); // F-G
            g.AdicionarAresta(v[4], v[7], 1); // E-H
            g.AdicionarAresta(v[7], v[8], 6); // H-I
            g.AdicionarAresta(v[7], v[9], 3); // H-J
            g.AdicionarAresta(v[8], v[9], 4); // I-J

            ap = g.Djikstra(new Vértice[] { v[0], v[4], v[9] }); // A, E e J são raízes

            for (int i = 0; i < 10; i++) {
                v[i] = ap.BuscarVértice(v[i].Nome);
            }

            Assert.IsTrue(ap.PossuiArestaParalela(v[0], v[3])); // A-D
            Assert.IsTrue(ap.PossuiArestaParalela(v[1], v[2])); // B-C
            Assert.IsTrue(ap.PossuiArestaParalela(v[2], v[4])); // C-E
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[5])); // E-F
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[6])); // E-G
            Assert.IsTrue(ap.PossuiArestaParalela(v[4], v[7])); // E-H
            Assert.IsTrue(ap.PossuiArestaParalela(v[8], v[9])); // I-J
            Assert.AreEqual(10, ap.QuantidadeVértices);
            Assert.AreEqual(7, ap.QuantidadeArestas);
            Assert.AreEqual(3, ap.ComponentesConexos());
        }


        /// <summary>
        /// Verifica se o grafo Kn gerado está correto
        /// </summary>
        /// <remarks>
        /// Cria um grafo ponderado g com vértices V1, V2, V3 e V4
        /// São adicionadas a g as arestas V1-V2, V1-V3, V1-V1, V2-V4, V1-V2
        /// Gera-se o grafo kn a partir de g
        /// Verifica-se:
        /// kn possui 4 vértices
        /// kn possui 6 arestas
        /// O valor da arestas em kn possuem o mesmo valor que em g
        /// </remarks>
        [TestMethod]
        public void GerarKn() {
            GrafoPonderado g, kn;

            g = new GrafoPonderado();

            g.AdicionarVértice("V1", "V2", "V3", "V4");
            g.AdicionarAresta("V1", "V2", 5);
            g.AdicionarAresta("V1", "V3", 8);
            g.AdicionarAresta("V1", "V1", 10);
            g.AdicionarAresta("V2", "V4", 7);
            g.AdicionarAresta("V2", "V1", 6);

            kn = (GrafoPonderado)g.GerarKN();

            Assert.AreEqual(4, kn.QuantidadeVértices);
            Assert.AreEqual(6, kn.QuantidadeArestas);
            Assert.AreEqual(5, ((ArestaPonderada)kn.BuscarVértice("V1").ProcurarAresta(kn.BuscarVértice("V2"))).Valor);
            Assert.AreEqual(8, ((ArestaPonderada)kn.BuscarVértice("V1").ProcurarAresta(kn.BuscarVértice("V3"))).Valor);
            Assert.AreEqual(7, ((ArestaPonderada)kn.BuscarVértice("V2").ProcurarAresta(kn.BuscarVértice("V4"))).Valor);
        }

        /// <summary>
        /// Teste da heurística de vizinho mais próximo
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria o grafo ponderado G com vértices V1, V2, V3, V4
        /// Adiciona as arestas V1-V2(5), V1-V3(8), V2-V4(7)
        /// Cria o grafo Kn a partir de G
        /// Procura-se o caminho por NearestNeighbour em Kn
        /// Verifica-se que o caminho dado é igual ao gabarito:
        /// V1, V2, V4, V3, V1
        /// </remarks>
        [TestMethod]
        public void NearestNeighbour() {
            GrafoPonderado g;
            Passeio p;
            Vértice[] v, gabarito;
            int i;

            g = new GrafoPonderado();
            g.AdicionarVértice("V1", "V2", "V3", "V4");
            g.AdicionarAresta("V1", "V2", 5);
            g.AdicionarAresta("V1", "V3", 8);
            g.AdicionarAresta("V2", "V4", 7);
            g = (GrafoPonderado)g.GerarKN();

            gabarito = new Vértice[] { g.BuscarVértice("V1"), g.BuscarVértice("V2"), g.BuscarVértice("V4"), g.BuscarVértice("V3"), g.BuscarVértice("V1") };

            p = g.NearestNeighbour(g.BuscarVértice("V1"));
            v = p.Listar();

            Assert.AreEqual(gabarito.Length, v.Length);
            for (i = 0; i < gabarito.Length; i++) {
                Assert.AreEqual(gabarito[i], v[i]);
            }
        }

        /// <summary>
        /// Teste da heurística 2-Opt
        /// </summary>
        [TestMethod]
        public void DoisOtimal() {
            GrafoPonderado g;
            Passeio init, result;

            g = new GrafoPonderado();
            g.AdicionarVértice("v1", "v2", "v3", "v4", "v5", "v6");
            g.AdicionarAresta("v1", "v2", 18);
            g.AdicionarAresta("v1", "v3", 17);
            g.AdicionarAresta("v1", "v4", 23);
            g.AdicionarAresta("v1", "v5", 12);
            g.AdicionarAresta("v1", "v6", 19);
            g.AdicionarAresta("v2", "v3", 26);
            g.AdicionarAresta("v2", "v4", 31);
            g.AdicionarAresta("v2", "v5", 20);
            g.AdicionarAresta("v2", "v6", 30);
            g.AdicionarAresta("v3", "v4", 16);
            g.AdicionarAresta("v3", "v5", 11);
            g.AdicionarAresta("v3", "v6", 9);
            g.AdicionarAresta("v4", "v5", 17);
            g.AdicionarAresta("v4", "v6", 19);
            g.AdicionarAresta("v5", "v6", 14);

            init = new Passeio();
            init.AdicionarVértice(g, "v1", "v2", "v3", "v4", "v5", "v6", "v1");

            result = g.KOpt2(init);

            Assert.AreEqual(99, result.Valor());
        }

    }
}
